#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-10-10 10:39 上午
# @Author  : yangdy
# @File    : 2020-10-10.142.环形链表 II
# @Software: PyCharmCE
from tools.my_methods import *


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        # p = head
        # while p:
        #     print(p.val, end='->')
        # print()
        m, i = {}, 0
        while head:
            if head not in m:
                m[head] = i + 1
            else:
                # return head
                break
            head = head.next
            i += 1
        # return None
        if not head:
            msg = 'no cycle'
        else:
            msg = f'tail connects to node index {m[head]-1}'
        return msg


def mk_list(data, pos):
    head = None
    if not data:
        return head
    head = ListNode(data[0])
    nodes = [head]
    for i in range(1, len(data)):
        p = ListNode(data[i])
        nodes[-1].next = p
        nodes.append(p)
    nodes[-1].next = nodes[pos] if pos >= 0 else None
    return head


questions = [
    ([3, 2, 0, -4], 1),
    ([1, 2], 0),
    ([1], -1),
]

work(questions=questions, func=lambda q: Solution().detectCycle(mk_list(q[0], q[1])))



